def search(s: str, p: str) -> int:
    n, m = 0, len(p)
    for i in range(0, len(s) - m):
        if s[i:i + m] == p:
            print('匹配位置', i)
            n += 1
    print('共找到', n, '个结果')
    return n

# KMP算法实现核心：next数组
def buildNext(s: str) -> list[int]:
    next = [-1] * len(s)
    for i in range(1, len(s)):
        nexti = next[i - 1] + 1
        while nexti >= 0 and s[nexti] != s[i]:
            nexti = next[nexti - 1] + 1 if nexti > 0 else -1
        next[i] = nexti
    return next

# KMP算法查找子串
def searchKMP(s: str, p: str) -> int:
    next = buildNext(p)
    j = 0
    for i in range(len(s)):
        while j >= 0 and s[i] != p[j]:
            if j == 0:
                j = -1
            else:
                j = next[j - 1] + 1
        j += 1
        if j == len(p):
            return i - j + 1
    return -1

# main
s, p = 'ababaababcb', 'ababc'
ans = searchKMP(s, p)
print('匹配的下标位置为:', ans)
